Home » Data Structure

Data Structure Searching Algorithms

Last updated : April 17, 2025

Searching is one of the fundamental operations performed on data structures. It is used to determine whether a particular element exists in a collection of data and, if it exists, to identify its location. Different searching algorithms are suitable for different types of data structures and arrangements of data.

Data Structure Searching

Searching is the process of finding an element in a given list. In this process, we check whether an item is available in the list or not.

A searching algorithm takes a collection of elements and a search value, commonly called the key or item. The algorithm compares the search value with elements in the collection and determines whether a matching element is present.

The efficiency of a searching algorithm depends on factors such as the number of elements, whether the data is sorted, how the data is stored, and how frequently searching operations are performed.

Applications of Searching

Searching is required in many areas of computer science and software development. Programs frequently need to locate records, values, files, or other information from a collection.

• Finding a particular value in an array or list.
• Searching records in databases.
• Finding a username or account in a collection.
• Searching files and directories.
• Finding an item in a sorted collection.
• Implementing lookup operations in software applications.
• Searching data used by other algorithms.

Types of Searching

• Internal Search: Searching is performed on main or primary memory.
• External Search: Searching is performed in secondary memory.

Internal Search

Internal searching is performed when the complete collection of data being searched can be stored in the main memory. Arrays, linked lists, and other in-memory data structures can be searched using internal searching techniques.

External Search

External searching is used when the amount of data is too large to fit entirely into main memory and is stored in secondary storage such as disks. External searching techniques are designed to reduce the number of expensive input and output operations required to locate data.

Complexity Analysis

Complexity analysis determines the number of resources (such as time and space) necessary to execute an algorithm.

There are two types of complexities:

1. Time Complexity
2. Space Complexity

Time Complexity

Time complexity describes how the running time of an algorithm changes as the size of the input increases. Searching algorithms can have significantly different time requirements depending on the organization of the input data.

Space Complexity

Space complexity describes the amount of additional memory required by an algorithm during execution. Some searching algorithms require only a small amount of additional memory, while others may require additional data structures or recursive call space.

Searching Techniques in Data Structures

There are three main types of searching techniques:

1. Linear or Sequential Search
2. Binary Search
3. Interpolation Search

These algorithms differ mainly in the way they locate an element. Linear search examines elements sequentially, binary search repeatedly divides a sorted search range, and interpolation search estimates the likely position of an element in uniformly distributed sorted data.

Linear or Sequential Search

This technique searches for an item from a list, starting from the 0th index to the Nth-1 index sequentially. If the item is found, its position is returned; otherwise, -1 or a failure status is returned.

Linear search does not require the elements of the list to be sorted. It starts at the first element and compares each element with the search item until a match is found or all elements have been examined.

How Linear Search Works

1. Start searching from the first element of the list.
2. Compare the current element with the search item.
3. If both values are equal, return the position of the element.
4. If they are not equal, move to the next element.
5. Continue until the item is found or the end of the list is reached.

Algorithm

LINEAR_SEARCH (LIST, N, ITEM, LOC, POS)
1. Set POS := 0;
2. Set LOC := 1;
3. Repeat STEPS a and b while LOC <= N
   a. If ( LIST[LOC] = ITEM) then 
      i.   SET POS := LOC;  
      ii.  return;
   b. Otherwise
      i.   SET LOC := LOC + 1;
4. return 

Pseudocode for Linear Search

LINEAR_SEARCH(LIST, N, ITEM)

1. Set POS = -1
2. For LOC = 0 to N - 1
      If LIST[LOC] = ITEM then
          POS = LOC
          Return POS
      End If
   End For
3. Return POS

Example of Linear Search

Consider the following list:

10, 25, 30, 45, 60

If the item to be searched is 45, the algorithm compares 45 with 10, then 25, then 30, and finally 45. Since the fourth element matches the search item, its position is returned.

Time Complexity of Linear Search

• Best Case: O(1), when the item is found at the first position.
• Average Case: O(n), because approximately n/2 elements may need to be checked.
• Worst Case: O(n), when the item is at the last position or does not exist.

Space Complexity of Linear Search

The iterative version of linear search uses a constant amount of additional memory. Therefore, its auxiliary space complexity is O(1).

Advantages of Linear Search

• Simple and easy to implement.
• Does not require the data to be sorted.
• Can be used with arrays and sequential collections.
• Works well for small datasets.
• Can stop immediately when the required element is found.

Disadvantages of Linear Search

• Can be slow for large datasets.
• May require checking every element in the worst case.
• Its performance does not improve significantly when the data is sorted.

Linear Search Implementation in C

#include <stdio.h>
#define SIZE 5

int LinearSearch(int ele[], int item) {
    int POS = -1;
    for (int LOC = 0; LOC < SIZE; LOC++) {
        if (ele[LOC] == item) {
            POS = LOC;
            break;
        }
    }
    return POS;
}

int main() {
    int ele[SIZE], item, pos;
    printf("\nEnter Items:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);
    pos = LinearSearch(ele, item);

    if (pos >= 0)
        printf("\nItem Found At Position : %d\n", pos + 1);
    else
        printf("\nItem Not Found In The List\n");

    return 0;
}

Binary Search

Binary search works on a sorted list. It repeatedly divides the search interval in half until the item is found or the interval becomes empty.

Unlike linear search, binary search does not examine every element one by one. It compares the search item with the middle element of the current range. Based on the comparison, one half of the search range is eliminated.

The list must be sorted before binary search is performed. For an ascending list, if the search item is smaller than the middle element, the search continues in the left half. If it is greater, the search continues in the right half.

How Binary Search Works

1. Set the lower boundary to the first element.
2. Set the upper boundary to the last element.
3. Calculate the middle position.
4. Compare the middle element with the search item.
5. If they are equal, return the position.
6. If the item is smaller, search the left half.
7. If the item is greater, search the right half.
8. Repeat until the item is found or the search range becomes empty.

Algorithm

BINARY_SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)
1. Set LOW := 1; HIGH := N;
2. Repeat while LOW <= HIGH
   a. Set MID := (LOW + HIGH)/2
   b. If ITEM = LIST[MID]
       i.   Set LOC := MID
       ii.  Return
   c. If ITEM < LIST[MID]
       i.   Set HIGH := MID - 1;
   d. Otherwise
       i.   Set LOW := MID + 1;
3. SET LOC := NULL
4. return

Pseudocode for Binary Search

BINARY_SEARCH(LIST, N, ITEM)

1. Set LOW = 0
2. Set HIGH = N - 1
3. While LOW <= HIGH
      MID = (LOW + HIGH) / 2

      If LIST[MID] = ITEM then
          Return MID

      Else If ITEM < LIST[MID] then
          HIGH = MID - 1

      Else
          LOW = MID + 1
      End If
   End While

4. Return -1

Example of Binary Search

Consider the sorted list:

10, 20, 30, 40, 50, 60, 70

Suppose the search item is 60. Binary search first checks the middle element. Since 40 is smaller than 60, the left half can be ignored. The algorithm then searches the remaining right half until 60 is found.

Time Complexity of Binary Search

• Best Case: O(1), when the middle element is the search item.
• Average Case: O(log n).
• Worst Case: O(log n).

The search space is divided approximately in half after each comparison. Therefore, the number of comparisons grows logarithmically as the number of elements increases.

Space Complexity of Binary Search

The iterative implementation of binary search requires a constant amount of additional memory and therefore has an auxiliary space complexity of O(1). A recursive implementation requires additional stack space.

Advantages of Binary Search

• Much faster than linear search for large sorted datasets.
• Requires only logarithmic comparisons in the average and worst cases.
• Simple to implement using an array.
• Efficient when the data is already sorted.

Disadvantages of Binary Search

• The data must be sorted before searching.
• Maintaining sorted data can require additional processing.
• It is not generally suitable for linked lists because accessing the middle element is not direct.

Binary Search Implementation in C

#include <stdio.h>
#define SIZE 5

int BinarySearch(int ele[], int item) {
    int POS = -1, LOW = 0, HIGH = SIZE - 1, MID;

    while (LOW <= HIGH) {
        MID = (LOW + HIGH) / 2;

        if (ele[MID] == item) {
            POS = MID;
            break;
        }
        else if (item > ele[MID]) {
            LOW = MID + 1;
        }
        else {
            HIGH = MID - 1;
        }
    }

    return POS;
}

int main() {
    int ele[SIZE], item, pos;

    printf("\nEnter Items In Sorted Order:\n");

    for (int i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);

    pos = BinarySearch(ele, item);

    if (pos >= 0)
        printf("\nItem Found At Position : %d\n", pos + 1);
    else
        printf("\nItem Not Found In The List\n");

    return 0;
}

Difference between Linear Search and Binary Search

Linear Search	Binary Search
Sorted list is not required.	Sorted list is required.
Can be used in linked list.	Not suitable for linked list.
Suitable for frequently changing lists.	Suitable for static lists.
High average comparisons.	Low average comparisons.
Worst-case time complexity is O(n).	Worst-case time complexity is O(log n).

Interpolation Search

Used when items are uniformly distributed. Improves on binary search by estimating the position of the element.

Interpolation search is a searching technique that works on a sorted array and estimates where the search item is likely to be located. Instead of always selecting the middle element as binary search does, it uses the values at the lower and upper boundaries to calculate a probable position.

Interpolation search is particularly effective when the values in the sorted array are distributed relatively uniformly. If the values are not uniformly distributed, its performance can approach that of linear search.

Interpolation Mid Formula

Mid = low + (high – low) * ((item – LIST[low]) / (LIST[high] – LIST[low]));

The formula estimates the position of the search item based on its value relative to the values at the lower and upper positions. The calculation should also handle the case where LIST[high] = LIST[low] to avoid division by zero.

How Interpolation Search Works

1. Start with the lowest and highest positions of the sorted array.
2. Check whether the search item lies within the range of the boundary values.
3. Calculate an estimated position using the interpolation formula.
4. Compare the element at the estimated position with the search item.
5. If the values are equal, return the position.
6. If the search item is greater, move the lower boundary forward.
7. If the search item is smaller, move the upper boundary backward.
8. Repeat until the item is found or the search range becomes invalid.

Algorithm

INTERPOLATION_SEARCH(LIST, N, ITEM)

1. Set LOW := 0
2. Set HIGH := N - 1

3. Repeat while LOW <= HIGH and
   ITEM >= LIST[LOW] and ITEM <= LIST[HIGH]

   a. If LIST[HIGH] = LIST[LOW] then
         If LIST[LOW] = ITEM then
             Return LOW
         Else
             Return -1
         End If
      End If

   b. Set MID :=
      LOW + ((ITEM - LIST[LOW]) * (HIGH - LOW))
      / (LIST[HIGH] - LIST[LOW])

   c. If LIST[MID] = ITEM then
         Return MID

   d. If LIST[MID] < ITEM then
         Set LOW := MID + 1

   e. Otherwise
         Set HIGH := MID - 1

4. Return -1

Pseudocode for Interpolation Search

INTERPOLATION_SEARCH(LIST, N, ITEM)

1. LOW = 0
2. HIGH = N - 1

3. While LOW <= HIGH AND
       ITEM >= LIST[LOW] AND
       ITEM <= LIST[HIGH]

      If LIST[LOW] = LIST[HIGH] then
          If LIST[LOW] = ITEM then
              Return LOW
          Else
              Return -1
          End If
      End If

      MID = LOW + ((ITEM - LIST[LOW]) * (HIGH - LOW))
            / (LIST[HIGH] - LIST[LOW])

      If LIST[MID] = ITEM then
          Return MID

      Else If LIST[MID] < ITEM then
          LOW = MID + 1

      Else
          HIGH = MID - 1
      End If

   End While

4. Return -1

Example of Interpolation Search

Consider the following sorted and relatively uniformly distributed list:

10, 20, 30, 40, 50, 60, 70, 80, 90

Suppose the search item is 70. Instead of automatically selecting the middle element, interpolation search estimates the position of 70 using the values at the lower and upper boundaries. Because the values are uniformly distributed, the estimated position can be close to the actual position of the item.

Time Complexity of Interpolation Search

• Best Case: O(1).
• Average Case: O(log log n) for uniformly distributed data.
• Worst Case: O(n) for poorly distributed data.

Space Complexity of Interpolation Search

The iterative interpolation search algorithm uses a constant amount of additional memory. Therefore, its auxiliary space complexity is O(1).

Advantages of Interpolation Search

• Average case time complexity is log₂(log₂(n)).
• Better performance than binary search on uniformly distributed data.
• Uses the value of the search item to estimate its position.
• Can be efficient for large, sorted, and uniformly distributed datasets.

Disadvantages of Interpolation Search

• Mid calculation is complex and increases execution time.
• Performs poorly on non-uniformly distributed data.
• Requires sorted data.
• Its worst-case performance can be O(n).
• It is generally designed for data structures that provide direct access to elements.

Interpolation Search Implementation in C

#include <stdio.h>
#define SIZE 9

int InterpolationSearch(int ele[], int item) {
    int LOW = 0;
    int HIGH = SIZE - 1;
    int MID;

    while (LOW <= HIGH && item >= ele[LOW] && item <= ele[HIGH]) {

        if (ele[LOW] == ele[HIGH]) {
            if (ele[LOW] == item)
                return LOW;
            else
                return -1;
        }

        MID = LOW + ((item - ele[LOW]) * (HIGH - LOW))
                  / (ele[HIGH] - ele[LOW]);

        if (ele[MID] == item) {
            return MID;
        }
        else if (ele[MID] < item) {
            LOW = MID + 1;
        }
        else {
            HIGH = MID - 1;
        }
    }

    return -1;
}

int main() {
    int ele[SIZE], item, pos;

    printf("\nEnter Items In Sorted Order:\n");

    for (int i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);

    pos = InterpolationSearch(ele, item);

    if (pos >= 0)
        printf("\nItem Found At Position : %d\n", pos + 1);
    else
        printf("\nItem Not Found In The List\n");

    return 0;
}

Difference Between Searching Algorithms

Feature	Linear Search	Binary Search	Interpolation Search
Data must be sorted	No	Yes	Yes
Search method	Sequential comparison	Repeatedly divides the search range	Estimates the probable position
Best Case	O(1)	O(1)	O(1)
Average Case	O(n)	O(log n)	O(log log n) for uniformly distributed data
Worst Case	O(n)	O(log n)	O(n)
Auxiliary Space	O(1)	O(1) iterative	O(1)
Suitable for	Small or unsorted data	Sorted data	Sorted and uniformly distributed data

Comparison of Searching Algorithms Based on Data

The choice of searching algorithm depends on the organization and characteristics of the data. Linear search is useful when the data is unsorted or the dataset is small. Binary search is generally preferred when data is sorted and direct access is available. Interpolation search can provide better average performance when sorted values are distributed uniformly.

Data Condition	Suitable Searching Technique
Small dataset	Linear Search
Unsorted dataset	Linear Search
Large sorted array	Binary Search
Sorted and uniformly distributed array	Interpolation Search
Frequently changing unsorted data	Linear Search

Searching in Arrays

Arrays are commonly used with searching algorithms because their elements can be accessed directly using an index. Linear search can be applied to both sorted and unsorted arrays, while binary and interpolation searches generally require sorted arrays.

When an array is sorted and contains a large number of elements, binary search can reduce the number of comparisons considerably compared with linear search. If the values are also relatively uniformly distributed, interpolation search may provide an additional advantage.

Searching in Linked Lists

Linear search is commonly used for linked lists because elements are accessed sequentially through links between nodes. Binary search is generally less suitable for a linked list because reaching the middle element requires traversing nodes rather than directly accessing an index.

For linked lists, the choice of searching technique should therefore consider the cost of accessing individual nodes in addition to the number of comparisons performed by the algorithm.

Factors Affecting Searching Performance

Several factors can affect the performance of a searching algorithm. The number of elements is important, but the organization of the data and the type of data structure also influence the choice of algorithm.

• Number of elements: Larger datasets generally require more efficient searching techniques.
• Data order: Sorted data allows algorithms such as binary and interpolation search to be used.
• Data distribution: Uniformly distributed values can improve interpolation search performance.
• Memory organization: Direct access to elements can make some algorithms more practical.
• Frequency of updates: Frequently changing data may make maintaining sorted order less desirable.
• Search frequency: Applications that perform many searches may benefit from investing in an appropriate data organization.